//
// Description: 5815. 扣分后的最大得分
// Created by Loading on 2021/7/18.
//

#include <bits/stdc++.h>

using namespace std;

long long maxPoints(vector<vector<int>> &points) {
    // m == points.length
    // n == points[r].length
    // 1 <= m, n <= 1e5
    /* 1 <= m * n <= 1e5 */
    /* 暴力计算的时间复杂度为 O(mn^2)，超时，需考虑 O(mn) 的时间复杂度 */

    /*
     * 动态规划数组 dp[i][j] 表示使用 point[i][j] 时的最大得分
     * 由于 dp[i] 只与 dp[i - 1] 有关，所以可以简化为一维数组
     */
    vector<long long> dp(points[0].begin(), points[0].end());
    for (int i = 1; i < points.size(); ++i) {
        // 临时数组，存放上一行对应位置可以取得的最大得分
        vector<long long> last_max(dp.size());

        /* 对于每一个格子，上一个格子的选取都可能是左上侧或右上侧，所以加权前缀和与加权后缀和都要考虑 */
        /* 加权前缀和思想 */
        // 当前位置左侧可以取得的最大得分
        long long left_max = 0;
        for (int j = 0; j < dp.size(); ++j) {
            // 每向后移动一位，需要扣分，权重 - 1
            left_max = max(left_max - 1, dp[j]);
            last_max[j] = left_max;
        }

        /* 加权后缀和思想 */
        // 当前位置右侧可以取得的最大得分
        long long right_max = 0;
        for (int j = (int) dp.size() - 1; j >= 0; --j) {
            // 每向前移动一位，需要扣分，权重 - 1
            right_max = max(right_max - 1, dp[j]);
            // 与加权前缀和的结果选取最大值
            last_max[j] = max(last_max[j], right_max);
            // 更新 dp 数组
            dp[j] = points[i][j] + last_max[j];
        }

//        // 更新 dp 数组
//        for (int j = 0; j < dp.size(); ++j) {
//            dp[j] = points[i][j] + last_max[j];
//        }
    }

    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector<vector<int>> points = {{1, 2, 3},
                                  {1, 5, 1},
                                  {3, 1, 1}};

    cout << maxPoints(points) << endl;
}